package com.lx.algorithm.kmp;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-12-13 11:43:59
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-12-13     张李鑫                     1.0         1.0 Version
 */
public class Kmp {


    public static int indexOf(String s1, String s2) {
        if (s1 == null || s2 == null || s2.length() > s1.length()) {
            return -1;
        }
        char[] str2 = s2.toCharArray();
        char[] str1 = s1.toCharArray();

        int str1Index = 0;
        int str2Index = 0;
        int[] arr = getNextArr(s2);
        while (str1Index < str1.length && str2Index < str2.length) {
            if (str1[str1Index] == str2[str2Index]) {
                str1Index++;
                str2Index++;
            } else if (arr[str2Index] >= 0) {
                str2Index = arr[str2Index];
            } else {
                str1Index++;
            }
        }
        return str2Index == str2.length ? str1Index - str2Index : -1;
    }

    private static int[] getNextArr(String s2) {
        if (s2.length() < 2) {
            return new int[]{-1};
        }
        int[] arr = new int[s2.length()];
        char[] chars = s2.toCharArray();
        arr[0] = -1;
        arr[1] = 0;
        int x = 2;
        int cn = 0;
        while (x < chars.length) {
            if (chars[x-1] == chars[cn]) {
                arr[x++] = ++cn;
            } else if (arr[cn] == -1) {
                arr[x++] = 0;
            } else {
                cn = arr[cn];
            }
        }
        return arr;
    }


    // for test
    public static String getRandomString(int possibilities, int size) {
        char[] ans = new char[(int) (Math.random() * size) + 1];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = (char) ((int) (Math.random() * possibilities) + 'a');
        }
        return String.valueOf(ans);
    }

    public static void main(String[] args) {
////        String a="acdddabccbabacddd";
////        int[] nextArr = getNextArr(a);
//        int possibilities = 5;
//        int strSize = 20000;
//        int matchSize = 50;
//        int testTimes = 200;
//        System.out.println("test begin");
//        long l = System.currentTimeMillis();
//        for (int i = 0; i < testTimes; i++) {
//            String str = getRandomString(possibilities, strSize);
//            String match = getRandomString(possibilities, matchSize);
//            if (str.indexOf(match)!=  indexOf(str, match)){
//                System.out.println("funck ");
//                break;
//            }
//        }
//        System.out.println("test finish");
        String a="abcdabcdabcd";
        int[] nextArr = getNextArr(a);

        System.out.println(123);
    }
}

